package com.leetcode.贪心;

/**
 * 给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
 * @author LZF
 *
 */
public class L122买卖股票的最佳时机II {
	/**
	 * 贪心：这道题是可以重复购买一只股票，但是只能持有 一股 股票，因此思路是：只要当前的价格低于第二天的价格，
	 * 就可以买入，第二天卖出；若第二天也低于第三天，第二天也买入，第三天卖出，以此类推。
	 */
	public static int maxProfit1(int[] prices) {

		int result = 0;
		for (int i = 0; i < prices.length - 1; i++) {
			if (prices[i] < prices[i + 1]) {
				result += prices[i + 1] - prices[i];
			}
		}
		return result;
    }
	
	/**
	 * 动态规划：dp[i][0]:表示第i天持有股票所得的现金
	 * dp[i][1]:表示第i天，不持有股票所得的最多现金
	 * dp[i][0]由两种状态的来：1、前一天就持有股票，因此保持现状，dp[i][0] = dp[i - 1][0]
	 * 			2、前一天没有持有股票，因此就是第i天买入股票，dp[i][0] = dp[i - 1][1] - prices[i]
	 * 			取两者最大，因此是要得到的现金最多
	 * dp[i][1]由两种状态的来：1、前一天就不持有股票，因此保持现状，dp[i][1] = dp[i - 1][1]
	 * 			2、前一天持有股票，因此就是第i天卖出股票，dp[i][1] = dp[i - 1][0] + prices[i]
	 * 			取两者最大，因此是要得到的现金最多
	 * @param prices
	 * @return
	 */
	public static int maxProfit2(int[] prices) {

		int[][] dp = new int[prices.length][2];
		dp[0][0] -= prices[0];
		dp[0][1] = 0;
		for(int i = 1;i < prices.length;i++) {
			dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
		}
		return dp[prices.length][1];
    }
	
	/**
	 * 动态规划--->优化（空间）实际上影响dp[i]的只有dp[i - 1]，因此用滚动数组可以实现
	 */
	public static int maxProfit3(int[] prices) {

		int[][] dp = new int[prices.length][2];
		dp[0][0] -= prices[0];
		dp[0][1] = 0;
		for(int i = 1;i < prices.length;i++) {
			dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
		}
		return dp[prices.length][1];
    }
}
